Welcome back to the cryptographic communication protocols lecture.

Last week we had a final look at theoretical concepts that are relevant to understand what modern messengers are doing.

For this we added our focus on what possible threat vectors are, what attackers could do, and what we want to prevent against and protect the security of our communication against by looking at weak randomness.

And we identified a building block that allows us to strengthen our protocols against that threat, which was the so-called key-updatable key encapsulation mechanism.

Which is basically a key encapsulation mechanism in which public key and secret key can both be updated in a way such that the public key, when being updated, never reveals any information about future or past keys that are established by the key encapsulation mechanism.

And also the secret key, when being updated, offers some form of forward secrecy.

And finally, the updates of the public keys and the secret keys need to stay in sync.

So basically when updating one of the two components, the update is fed with some associated data.

And as long as the associated data stays in sync for both updates, the keys work compatible.

But as soon as there is a difference between the update associated data, the keys become incompatible.

And so future keys that are established with the public key will not be leaked to someone who has the secret key, which was updated incompatibly.

The very naive construction of key-updatable CHEMS is based on hierarchical identity-based encryption.

And we remembered that hierarchical identity-based encryption is pretty inefficient.

The basic idea was that we have the tree of identities and an update of the secret key is just a delegation to a lower level identity.

And the update of the public key is just adding the associated data string to the strings of updates that happened so far.

And that means that we have a very deep depth, an unbounded depth in the HIVE,

which is not a property that we would like to have because unbounded depth HIVEs are expensive.

And so we looked at very, very briefly and sketched the idea of a different construction that just works with bounded depth HIVEs.

And the idea is basically to split the updates into smaller strings, smaller strings of updates or smaller lists of updates.

And each of these lists is then called an epoch.

And these epochs are arranged in a tree similar to the idea of how forward secure key encapsulation mechanisms work.

So we have a binary tree that has epochs.

And these epochs somewhat or this binary tree of epochs is basically similar to how forward secure key encapsulation mechanisms work.

But then in these epochs, we then have updates that are based on or that that pay attention to the associated data strings with which we do updates.

And so we basically combine these two ideas to have a much better, much more efficient form of key, key updateable key encapsulation mechanisms.

As I said, these ideas are still very theoretical because none of the messengers that we know in practice implements these things.

And for us, it's more the idea of understanding what could be done.

What are the tools that we have?

Where are the open problems?

Where are the open questions in the research literature?

So one of the open problems is, for example, building a key encapsulation or key updateable key encapsulation mechanism from even more efficient building blocks such that eventually we could could use these things.

But before we solve these problems, we first need to understand how the practical messengers actually look like.

And this is the focus of today's lecture.

So today we will be looking at the key encapsulation mechanisms.

And this is the focus of today's lecture.

So today we look at the double ratchet.

Algorithm, we look at group messaging in general.

Because the double ratchet protocol or the double ratchet algorithm is a messaging protocol that is useful for two party conversations.

And if we would like to scale from two party to group messaging, the first idea that comes to mind is that you just have pairwise channels between all group members.

And so one group message becomes n single messages or n minus one messages sent from myself to the remaining group members.

And this is inefficient.

And because this is inefficient, there are several alternatives that could be used.

And one of these alternatives is technically a little bit more challenging.

And for that reason, we'd take a look deeper at that later in today's lecture, but also even more detailed in a slight variant or alternative next lecture.

And this is the tree based if you have the tree based if you have allows us to build a group messaging protocol with sublinear communication overhead.

OK, we will see more about that at the end of the lecture, as I said, but it is pretty relevant in the sense that the tree based if you have an idea in its variant that we will look at next week has been standardized last year standardized for group messaging.

The MLS messaging standard is something that is aimed to be deployed in big messengers, for example, in Cisco's WebEx.

Also, Facebook and WhatsApp are doing some preliminary research on how to implement it or embed it in their systems.

And so all of these things that we talk about today and next week are really deployed in practice or will be deployed in practice with billions of users.

OK, so we start with the double ratchet algorithm.